package offer.day17;

public class No27BinaryTreeMirror {
    /*
     * 面试题27：二叉树的镜像
     * 题目：请完成一个函数，输入一颗二叉树，该函数输出它的镜像。
     * 二叉树节点定义：
     * struct BinaryTreeNode{
     * 	int m_nValue;
     * 	BinaryTreeNode* m_pLeft;
     * 	BinaryTreeNode* m_pRight;
     * }
     *
     *
     * 思路：递归的思想
     * 从根节点开始，判断是否有左子树或者右子树，然后交换两个子树；
     * 然后再继续判断左子树，看是否有左右子树，有的话交换左右子树，
     * 。。。。。。直到为空或者为叶子节点时，返回即可。
     * 这是一个迭代的过程： 1>  结束内容：if（）return；
     * 				    2>  数据处理内容：change(left<-->right)
     * 				    3>  递归调用：若左子树||右子树不为空，则交换左右子树
     *
     * 输出二叉树，使用先序遍历的方式遍历二叉树进行输出。
     *
     * */
    public static void main(String[] args) {

        No27BinaryTreeMirror b = new No27BinaryTreeMirror();

        BinaryTreeNode root1 = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(8);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(9);
        BinaryTreeNode four = new BinaryTreeNode(2);
        BinaryTreeNode five = new BinaryTreeNode(4);
        BinaryTreeNode six = new BinaryTreeNode(7);

        root1.left = one;
        root1.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = null;
        three.left = null;
        three.right = null;
        four.left = five;
        four.right = six;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        System.out.println("以先序遍历的方式输出二叉树：");
        if(root1 != null) {
            PrintBinaryTree(root1);
            //未通过b调用PrintBinaryTree()函数，所以该函数要设置为static形式
        }
        b.BinaryTreeMirror(root1);
        //通过对象b调用BinaryTreeMirror()函数，所以该函数不用static
        System.out.println("以先序遍历方式输出二叉树的镜像：");
        if(root1 != null) {
            PrintBinaryTree(root1);
            //未通过b调用PrintBinaryTree()函数，所以该函数要设置为static形式
        }
    }

    public void BinaryTreeMirror(BinaryTreeNode root){
        if(root==null) return;
        if(root.left==null&& root.right==null) return;
        BinaryTreeNode tmp=root.left;
        root.left=root.right;
        root.right=tmp;
        if(root.left!=null){
            BinaryTreeMirror(root.left);
        }
        if(root.right!=null){
            BinaryTreeMirror(root.right);
        }
    }


    //输出二叉树节点值   根左右（先序遍历二叉树）
    public static void PrintBinaryTree(BinaryTreeNode root1) {
        System.out.println(root1.val);
        if(root1.left == null && root1.right == null) {
            return;
        }
        if(root1.left != null) {
            PrintBinaryTree(root1.left);
        }
        if(root1.right != null) {
            PrintBinaryTree(root1.right);
        }
    }}
